#include <stdio.h>
#define maxSize 6

typedef struct
{
    /* data */
    int data;   //数据域
    int cur;    //游标
}StaticLinkList;

//将结构体数组中所有分量链接到备用链表中
void spareLinkList(StaticLinkList* linkList);
//初始化静态链表
int initLinkList(StaticLinkList* linkList);
//输出函数
void displayLinkList(StaticLinkList* linkList, int head);
//从备用链表上摘下空闲节点的函数
int mallocLinkList(StaticLinkList* linkList);

int main(int argc, char* argv[]) {
    //创建静态链表
    StaticLinkList linkList[maxSize];
    spareLinkList(linkList);
    //初始化
    int head = initLinkList(linkList);
    printf("静态链表为：\n");
    displayLinkList(linkList, head);
    return 0;
}

//创建备用链表
void spareLinkList(StaticLinkList* linkList) {
    //数据链表未初始化之前, 所有位置应被链接在备用链表上
    for(int i=0; i<maxSize; i++) {
        linkList[i].data = -1;
        linkList[i].cur = i+1;
    }
    linkList[maxSize-1].cur = 0;
    // for(int i=0; i<maxSize; i++) {
    //     printf("data %d ",linkList[i].data);
    //     printf("cur %d\n",linkList[i].cur);
    // }
    // printf("--\n");
}

//获取已分配空间
int mallocLinkList(StaticLinkList* linkList) {
    //若备用链表非空，则返回待分配的结点下标，否则返回 0（当分配最后一个结点时，该结点的游标值为 0）
    //备用链表的表头
    int i = linkList[0].cur;
    //如果备用链表的表头游标变量不为 0， 
    if(linkList[0].cur) {
        linkList[0].cur = linkList[i].cur;
    }
    // for(int i=0; i<maxSize; i++) {
    //     printf("data %d ",linkList[i].data);
    //     printf("cur %d\n",linkList[i].cur);
    // }
    // printf("----\n");
    //返回分配的结点下标
    return i;
}


//初始化静态链表
int initLinkList(StaticLinkList* linkList) {
    //获取备用链表表头游标变量,同时分配linkList[1]空间
    int head = mallocLinkList(linkList);
    //声明一个变量，把它当指针使，指向链表的最后的一个结点，因为链表为空，所以和头结点重合
    int tempIndex = head;
    //将指向链表最后一个结点的指针后移
    //linkList[index].data = index;
    for(int i=1; i<maxSize-2; i++) {
        //从备用链表中拿出空闲的游标
        int j = mallocLinkList(linkList);
        //将申请的空闲分量链接在当前静态链表的最后一个数据结点后面
        linkList[tempIndex].cur = j;
        //给新申请的分量的数据域初始化
        linkList[j].data = i;
        //将指向链表最后一个结点的指针后移
        tempIndex = j;
        //printf("tempIndex %d\n", tempIndex);
    }
    //新的链表最后一个结点的指针设置为0
    linkList[tempIndex].cur = 0;
    return head;
}

//打印静态链表
void displayLinkList(StaticLinkList* linkList, int head) {
    //tempIndex准备做遍历使用
    int tempIndex = head;
    //printf("tempIndex %d\n", tempIndex);
    //如果静态链表的游标变量不为 0（即还有后继元素）
    while(linkList[tempIndex].cur) {
        //数据链表头遍历打印
        printf("data %d,cur %d\n",linkList[tempIndex].data,linkList[tempIndex].cur);
        tempIndex = linkList[tempIndex].cur;
    }
    //备用链表头打印
    printf("data %d,cur %d\n",linkList[tempIndex].data,linkList[tempIndex].cur);

}